package com.xiaoyu.sort.basic;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 归并排序
 * @author: YuWenYi
 * @create: 2021-04-30 08:34
 **/
public class MergeSort {

    //800万数据在1.45秒左右,仅比快速排序慢
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
       if (left < right){
           //先分,再合,采用分治法
           int mid = (left + right)/2;
           //把左边拆分
           mergeSort(arr,left,mid,temp);
           //把右边拆分
           mergeSort(arr,mid+1,right,temp);
           //再递归合并
           System.out.println("left="+left+"--right="+right);
           merge(arr,left,mid,right,temp);   //merge的次数的arr.length-1,为线性的!!
       }
    }

    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int t = 0;  //记录临时数组temp中下一个可插入数据的位置
        int l = left;   //左边数组的初始化索引
        int r = mid + 1; //右边数组的初始化索引

        //左右比较,然后把大部分较小的数字放到temp数组中,当某个
        while (l <= mid && r <= right){
            //如果左边数组的元素小于右边数组的元素,那么就把左边数组的该元素放入temp数组中(从左往右)
            //然后l++,代表左边数组已经放了一个数组进去了,t++,代表上一个位置已经有元素了,指向下一个可插入的位置
            if (arr[l] <= arr[r]){
                temp[t++] = arr[l++];
            }else{  //反之,右边数组的值小于左边数组,那么就反着来
                temp[t++] = arr[r++];
            }
        }
        //下面两个while只可能进入一个,因为上面的循环必然是左边不满足l <= mid或者右边不满足r <= right导致的循环退出
        while (l <= mid){
            temp[t++] = arr[l++];
        }
        while (r <= right){
            temp[t++] = arr[r++];
        }

        //最后将temp数组中排好序的元素拷贝到arr中
        t = 0;
        while (left <= right){
            arr[left++] = temp[t++];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{-9,-2,-17,4,6,-20,9,8,-16,50,4,15};
        int[] nums = new int[]{6,9,1,8,2,3,5,4,7,0};
        int[] temp = new int[nums.length];
        mergeSort(nums,0,nums.length-1,temp);
        System.out.println(Arrays.toString(arr));

        //速率测试  800万1.45秒
/*        int[] bigData = new int[80000];
        int[] tempForBD = new int[bigData.length];
        for (int i = 0; i < 80000; i++) {
            bigData[i] = (int)(Math.random() * 80000);
        }
        long start = System.currentTimeMillis();
        mergeSort(bigData,0, bigData.length-1,tempForBD);
        long stop = System.currentTimeMillis();
        System.out.println((stop-start)/1000.0);*/

    }

}
